package com.wzq.solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution40 {
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> rstList = new ArrayList<List<Integer>>();

        Arrays.sort(candidates);

        foo(candidates,0,target,0,new ArrayList<Integer>(),rstList);
        return rstList;
    }


    public static void foo(int[] arr,int i,int target,int sum,List<Integer> sList,List<List<Integer>> rstList){

        if(target == sum){
            rstList.add(sList);
        }else{

            for(int t=i;i<arr.length && sum + arr[i] <= target;i++){
                if(i>t && arr[i] == arr[i-1]){
                    continue;
                }
                List<Integer> newList = new ArrayList<Integer>(sList);
                newList.add(arr[i]);
                foo(arr,i+1,target,sum+arr[i],newList,rstList);
            }
        }
    }
    public static void main(String[] args) {
        System.out.println(combinationSum2(new int[]{10,1,2,7,6,1,5},8));
    }
}